//132 分割回文串 II
//给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。 
//
// 返回符合要求的最少分割次数。 
//
// 示例: 
//
// 输入: "aab"
//输出: 1
//解释: 进行一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
// 
// Related Topics 动态规划


package leetcode.editor.cn;

import java.util.Arrays;

/**
 * 解题思路：
 * boolean[][]  isPalin = new boolean[n][n];表示i到j是否回文。
 * 然后再用dp遍历。
 * 这样效率会高点哟。
 * 两重的dp，
 */
public class A132PalindromePartitioningIi {
    public static void main(String[] args) {
        Solution solution = new A132PalindromePartitioningIi().new Solution();
        System.out.println("佛祖保佑");
        System.out.println("\uD80C\uDC09\uD80C\uDC02\uD80C\uDC03\uD80C\uDC10");
        solution.minCut("aab");

    }
    //leetcode submit region begin(Prohibit modification and deletion)

    class Solution {
        public int minCut(String s) {
            int n = s.length();
            int[] f = new int[n + 1];
            f[0] = -1;

            for (int i = 1; i <= n; i++) {
                f[i] = i;
                for (int j = 0; j < i; j++) {
                    if (isPal(s.substring(j, i))) {
                        f[i] = Math.min(f[j] + 1, f[i]);
                    }
                }
                System.out.println(Arrays.toString(f));
            }

            return f[n];
        }

        boolean isPal(String s) {
            int left = 0, right = s.length() - 1;
            while (left < right) {
                if (s.charAt(left++) != s.charAt(right--)) {
                    return false;
                }
            }
            return true;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
